import copy
from collections import defaultdict

nums = [
    345590635693812, 411735179294186, 190029355501347, 973598561303630, 18202819016954,
    739089526396984, 41064501651340, 287075700776565, 458062562307032, 723278851371706,
    997720296178889, 470475557480472, 329586527903215, 907379737442406, 631284976214798,
    301204036247736, 747294692547790, 914091289062262, 144070679727924, 988094642462741,
    413975599277375, 835461430976017, 344371572186185, 646160866308904, 880407857470630,
    794629069521762, 462180977651587, 342038139286302, 854772507978666, 694223418935656,
    567502001946067, 881035713848915, 840605474892139, 324727089144326, 226008847101330,
    65143946718125, 499249957077991, 245803813100131, 447887480320685, 658036302578844
]

total = sum(nums)
target = total // 2

# 初始化 dp 数组，dp[i] 表示是否能凑出和为 i
dp = defaultdict(lambda: False)
dp[0] = True

for num in nums:
    for j in copy.copy(list(dp.keys())):
        dp[j + num] = True

# 找到最大的可以凑出的和
max_sum = max(dp.keys())

# 计算两队的差值
diff = abs(total - 2 * max_sum)
print(diff)
